package 数组.easy;

/**
 * EASY
 */

/**
 * @author Lw中
 * @date 2020/8/2 19:16
 *
 */
public class YiLingWuYi {

    /**
     * 使用插入排序
     * @param heights
     * @return
     */
    public static int heightChecker(int[] heights) {
        int[] test = new int[heights.length];
        System.arraycopy(heights, 0, test, 0, heights.length);
        int sum = 0;
        for (int i=1; i<heights.length; i++) {
            int value = heights[i];
            int j = i -1;
            for(; j>=0; --j) {
                if (heights[j] > value) {
                    heights[j+1] = heights[j];
                } else {
                    break;
                }
            }
            heights[j+1] = value;
        }
        for (int k=0; k<heights.length; k++) {
            if (heights[k] != test[k]) {
                sum = sum + 1;
                System.out.println(heights[k]);
            }
        }
        return sum;
    }

    /**
     * 使用计数排序
     * @param heights
     * @return
     */
    public static int heightChecker1(int[] heights) {
        int[] array = new int[101];
        for (int index : heights) {
            array[index]++;
        }
        int n = 0;
        for(int i=1, j=0; i<array.length; i++) {
            while (array[i]-->0) {
                if(heights[j++] != i) {
                    n++;
                }
            }
        }
        return n;
    }

    public static void main(String[] args) {
        int[] heights = {1,2,3,4,5,6};
        int result = heightChecker(heights);
        int result1 = heightChecker1(heights);
        System.out.println(result);
        System.out.println(result1);
    }

}
